package com.jdaw.datastructure.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
    }

    public static void radixSort(int[] arr){
        //先要得到最大数的位数，来决定for循环几次
        int max=0;
        for(int i=0;i<arr.length;i++){
            if(max<arr[i]){
                max=arr[i];
            }
        }
        int count=0;
        while(max>0){
            count++;
            max/=10;
        }
        System.out.println(count);
        //用二维数组表示10个桶,占用空间大，属于空间换时间
        int[][] bucket=new int[10][arr.length];
        //定义一个一维数组记录每个桶每次放入的数量
        int[] bucketElementCounts=new int[10];

        for(int j=0,n=1;j<count;j++,n*=10){
            //第一轮
            for(int i=0;i<arr.length;i++){
                //取出第j位
                int digitOfElement=arr[i]/n%10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[i];
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个顺序放入原来数组
            int index=0;
            for(int k=0;k<bucket.length;k++){
                if(bucketElementCounts[k]!=0){
                    //循环第k个桶把数据加到arr中
                    for(int i=0;i<bucketElementCounts[k];i++){
                        arr[index]=bucket[k][i];
                        index++;
                    }
                }
                //第j轮结束要把bucketElementCounts置零
                bucketElementCounts[k]=0;
            }
        }
        System.out.println(Arrays.toString(arr));
//
//
//        //第一轮
//        for(int i=0;i<arr.length;i++){
//            //取出个位
//            int digitOfElement=arr[i]%10;
//            bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[i];
//            bucketElementCounts[digitOfElement]++;
//        }
//        //按照这个顺序放入原来数组
//        int index=0;
//        for(int k=0;k<bucket.length;k++){
//            if(bucketElementCounts[k]!=0){
//                //循环第k个桶把数据加到arr中
//                for(int i=0;i<bucketElementCounts[k];i++){
//                    arr[index]=bucket[k][i];
//                    index++;
//                }
//            }
//            //第一轮结束要把bucketElementCounts置零
//            bucketElementCounts[k]=0;
//        }
//        System.out.println(Arrays.toString(arr));
//
//        //第二轮
//        for(int i=0;i<arr.length;i++){
//            //取出个位
//            int digitOfElement=arr[i]/10%10;
//            bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[i];
//            bucketElementCounts[digitOfElement]++;
//        }
//        //按照这个顺序放入原来数组
//        index=0;
//        for(int k=0;k<bucket.length;k++){
//            if(bucketElementCounts[k]!=0){
//                //循环第k个桶把数据加到arr中
//                for(int i=0;i<bucketElementCounts[k];i++){
//                    arr[index]=bucket[k][i];
//                    index++;
//                }
//            }
//            //第二轮结束要把bucketElementCounts置零
//            bucketElementCounts[k]=0;
//        }
//        System.out.println(Arrays.toString(arr));
//
//        //第三轮
//        for(int i=0;i<arr.length;i++){
//            //取出个位
//            int digitOfElement=arr[i]/100%10;
//            bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[i];
//            bucketElementCounts[digitOfElement]++;
//        }
//        //按照这个顺序放入原来数组
//        index=0;
//        for(int k=0;k<bucket.length;k++){
//            if(bucketElementCounts[k]!=0){
//                //循环第k个桶把数据加到arr中
//                for(int i=0;i<bucketElementCounts[k];i++){
//                    arr[index]=bucket[k][i];
//                    index++;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
    }

}
